﻿#pragma once
#include "Index.h"

/**
 * 数组中唯一只出现一次的数字
 * 
 * 在一个数组中除一个数字只出现一次之外,其他数字都出现了三次.请找出那个只出现一次的数字.
 */
class IFindNumAppearOnlyOnce
{
public:
	virtual int findNumAppearOnce(std::vector<int>& nums) = 0;
};

class FindNumAppearOnlyOnce
{
public:
	class Bit:public IFindNumAppearOnlyOnce
	{
	public:
		int findNumAppearOnce(std::vector<int>& nums) override
		{
			//每个数字的比特位上累加和
			std::array<int, 32> bitAcc={0};
			for(int& num : nums)
			{
				for (int i = 0; i < 32; ++i)
				{
					if (num & (1 << i))
						bitAcc[i]++;
				}
			}
			//对于出现次数为3的数,比特位上的累加和能够整除3
			//如果比特位上的累加和能整除3,则出现一次的数在该比特位上为0.否则就是为1
			int result = 0;
			for(int i=0;i<32;++i)
			{
				if (bitAcc[i] % 3 != 0)
					result |= (1 << i);
			}

			return result;
		}
	};
};

#ifdef DEV_TEST
#include "gtest/gtest.h"
TEST(FindNumAppearOnlyOnceTest, findNumAppearOnce)
{
	TEST_SOLUTION1(IFindNumAppearOnlyOnce, FindNumAppearOnlyOnce::Bit, &)
	{
		__slnTestor.setTestTimes(1000);
		std::vector<int> nums;
		for (int i = 0; i < 100; ++i)
		{
			int duplicate = TestingUtil::randIntBetween(-100, 100);
			for(int k=0;k<3;++k)
				nums.emplace_back(duplicate);
		}
			
		int once = TestingUtil::randIntBetween(1000, 10000);
		nums.emplace_back(once);

		std::random_device rd;
		std::mt19937 mt(rd());
		std::shuffle(nums.begin(), nums.end(), mt);

		int resultOnce= solution->findNumAppearOnce(nums);
		EXPECT_EQ(resultOnce, once);
	};
}
#endif